// 最长回文子串

package Leetcode;

import java.lang.StringBuffer;

class solution_005 {
	public String longestPalindrome(String s) {
		if (s.length() == 0)
			return "";
		if (s.length() == 1)
			return s;
		int max = 0;
		String result = "";
		for (int i = 0; i < s.length(); i++) {
			for (int j = i + 1; j <= s.length(); j++) {
				String substring = s.substring(i, j);
				String reverse = new StringBuffer(substring).reverse().toString();
				if (substring.compareTo(reverse) == 0 && (j - i) > max) {
					max = j - i;
					result = substring;
				}
			}
		}
		return result;
	}
}

// 上述写法超时
// 尝试使用动态规划思想，假设s[i][j]表示字串si~sj
// 递推：如果s[i-1][j+1]为回文串且si=sj，那么s[i][j]也是回文串，
// 初始化：s[i][i]为回文串，因为只有一个字符
public class Solution005 {
	public static void main(String[] args) {

	}

	public String longestPalindrome(String s) {
		int length = s.length();
		if (length <= 1)
			return s;
		int maxLength = 1;
		int begin = 0;
		// 用dp[i][j] 表示s[i~j]是否为回文串
		boolean[][] dp = new boolean[length][length];
		// 初始化，一个字符一定是回文串
		for (int i = 0; i < length; i++)
			dp[i][i] = true;
		char[] charArray = s.toCharArray();
		// 先固定左边界，再固定右边界，所以循环里先执行子串长度循环
		// L 代表串的长度，j表示串的右边界
		for (int L = 2; L <= length; L++) {
			for (int i = 0; i < length; i++) {
				int j = i + L - 1;
				// 如果j越界则停止
				if (j >= length)
					break;
				if (charArray[i] != charArray[j])
					dp[i][j] = false;
				else {
					// 长度为2且头尾相等则一定回文 注意长度为2时没有状态转移方程
					if (j - i < 3)
						dp[i][j] = true;
					else
						dp[i][j] = dp[i + 1][j - 1];
				}
				// 当前串是回文串
				if (dp[i][j] && (j - i + 1) > maxLength) {
					maxLength = j - i + 1;
					begin = i;
				}
			}
		}
		return s.substring(begin, begin + maxLength);
	}
}
